翻訳と辞書 Words near each other ・ Ukiyo-zōshi ・ Ukiyoburo ・ Ukiyotei ・ UKK ・ Ukk ・ UKK Bosna ・ Ukkadai ・ Ukkadai estate ・ Ukkadam ・ Ukkadam Lake ・ Ukkadam-Valankulam Lake ・ Ukkali ・ Ukkin ・ Ukko ・ Ukko Hietala ・ Ukkonen's algorithm ・ Ukkovaara ・ Ukku Stadium ・ Ukkulankulam ・ Ukkurey ・ Ukkusiksalik National Park ・ Ukkusissat ・ Ukkusissat (mountain) ・ Ukkusissat Heliport ・ UKL ・ UKLA ・ Uklanamandi ・ Ukleisee ・ Ukleja (river) ・ Uklejka Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Ukkonen's algorithm ： ウィキペディア英語版 Ukkonen's algorithm In computer science, Ukkonen's algorithm is a linear-time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995. The algorithm begins with an implicit suffix tree containing the first character of the string. Then it steps through the string adding successive characters until the tree is complete. This order addition of characters gives Ukkonen's algorithm its "on-line" property. The original algorithm presented by Peter Weiner proceeded backward from the last character to the first one from the shortest to the longest suffix. A simpler algorithm was found by Edward M. McCreight, going from the longest to the shortest suffix. The naive implementation for generating a suffix tree going forward requires ''O''(''n''2) or even ''O''(''n''3) time complexity in big O notation, where ''n'' is the length of the string. By exploiting a number of algorithmic techniques, Ukkonen reduced this to ''O''(''n'') (linear) time, for constant-size alphabets, and ''O''(''n'' log ''n'') in general, matching the runtime performance of the earlier two algorithms. ==References== 〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ukkonen's algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.